//
//  DivideAndConquer.swift
//  ArithmeticClass15
//
//  Created by xiangzuhua on 2021/1/27.
//

// 分治算法
class DivideAndConquer {
    
    static var num: Int = 0
    /// 计算一个整型数组的逆序度
    /// - Parameter arr: 要计算的数组
    /// - Returns: 逆序度
    class func count(_ arr: inout[Int]) -> Int {
        num = 0
        let number = arr.count
        reverseCount(&arr, startIndex: 0, endIndex: number - 1)
        return num
    }
    
    class func  reverseCount(_ arr: inout[Int], startIndex st : Int, endIndex en: Int) {
        if st >= en {// 已分解到最小单位
            return
        }
        
        let middle = (en + st) / 2// 取中间位置
        reverseCount(&arr, startIndex: st, endIndex: middle)
        reverseCount(&arr, startIndex: middle + 1, endIndex: en)
        merge(&arr, startIndex: st, middleIndex: middle, endIndex: en)
    }
    
    class func merge(_ arr: inout[Int], startIndex sta: Int, middleIndex mid: Int, endIndex end: Int){
        var i = sta
        var j = mid + 1
        var k = 0
        var tempArr = [Int](repeating: 0, count: end - sta + 1)
        // 两个指针，分别从两个区间取值对比，将小的放入临时数组，以得到一个有序数组
        while i <= mid && j <= end {
            if arr[i] <= arr[j] {
                tempArr[k] = arr[i]
                k += 1
                i += 1
            } else {
                num += mid - i + 1// 记录逆序对的个数
                tempArr[k] = arr[j]
                k += 1
                j += 1
            }
        }
        
        while i <= mid {
            tempArr[k] = arr[i]
            k += 1
            i += 1
        }
        
        while j <= end {
            tempArr[k] = arr[j]
            k += 1
            j += 1
        }
        for (index, item) in tempArr.enumerated() {
            arr[sta + index] = item
        }
    }
}
